package cn.fcraft.utils;

public class Math {
    /** 取最大公因数
     * 不严格要求a>=b,因为如果a<b,a%b为a,会在else分支代入(b,a),多进行一次运算而已
     * 欧几里得算法：用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。
     * @param a 一个非零整数
     * @param b 一个非零整数
     * @return 返回最大公因数,若a==0||b==0,返回1
     */
    public static int getGcd(int a, int b) {
        if (a == 0 || b == 0) return 1;
        int r = a % b;//r为余数
        while (r != 0) {
            a = b;
            b = r;
            r = a % b;
        }
        return b;
    }
}
